package com.zklh.leetcode.top100;

import com.zklh.leetcode.tree.model.ListNode;

/**
 * 排序链表算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/9/22
 */
public class Solution148 {
    public ListNode sortList(ListNode head) {
        int size = 0;
        ListNode temp = head;
        while (temp != null) {temp = temp.next; size ++;}
        return mergeSort(head, size);
    }


    public ListNode mergeSort(ListNode head, int size) {
        if (size == 0) {
            return null;
        }
        if (size == 1) {
            head.next = null;
            return head;
        }
        if (size == 2) {
            head.next.next = null;
            if (head.val > head.next.val) {
                int temp = head.val;
                head.val = head.next.val;
                head.next.val = temp;
            }
            return head;
        }

        ListNode frontHead = head;
        ListNode backHead = head;
        for (int i = 0; i < size / 2; i++) {
            backHead = backHead.next;
        }

        frontHead = mergeSort(frontHead, size/2);
        backHead = mergeSort(backHead, size - size/2);

        ListNode preHead = new ListNode();
        ListNode current = preHead;

        while (frontHead != null || backHead != null) {
            if(frontHead != null && backHead != null) {
                if (frontHead.val < backHead.val) {
                    current.next = frontHead;
                    frontHead = frontHead.next;
                } else {
                    current.next = backHead;
                    backHead =backHead.next;
                }
            } else if (frontHead == null) {
                current.next = backHead;
                backHead = backHead.next;
            } else {
                current.next = frontHead;
                frontHead = frontHead.next;
            }
            current = current.next;
        }
        current.next = null;
        return preHead.next;
    }

    public static void main(String[] args) {
        // given
        ListNode head = new ListNode(-1);
        head.next = new ListNode(5);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(0);

        // when
        Solution148 solution148 = new Solution148();
        head = solution148.sortList(head);

        //then
        System.out.println(head);
    }
}